package com.zjsru.plan2025.oneday;

import java.util.HashMap;
import java.util.Map;

/**
 * 2588. 统计美丽子数组数目
 *
 * @Author: cookLee
 * @Date: 2025-03-06
 */
public class BeautifulSubarrays {

    /**
     * 主
     * \
     * 选择两个满足 0 <= i, j < nums.length 的不同下标 i 和 j 。
     * 选择一个非负整数 k ，满足 nums[i] 和 nums[j] 在二进制下的第 k 位（下标编号从 0 开始）是 1 。
     * 将 nums[i] 和 nums[j] 都减去 2k 。
     * \
     * 输入：nums = [4,3,1,2,4]
     * 输出：2
     * 解释：nums 中有 2 个美丽子数组：[4,3,1,2,4] 和 [4,3,1,2,4] 。
     * - 按照下述步骤，我们可以将子数组 [3,1,2] 中所有元素变成 0 ：
     * - 选择 [3, 1, 2] 和 k = 1 。将 2 个数字都减去 21 ，子数组变成 [1, 1, 0] 。
     * - 选择 [1, 1, 0] 和 k = 0 。将 2 个数字都减去 20 ，子数组变成 [0, 0, 0] 。
     * - 按照下述步骤，我们可以将子数组 [4,3,1,2,4] 中所有元素变成 0 ：
     * - 选择 [4, 3, 1, 2, 4] 和 k = 2 。将 2 个数字都减去 22 ，子数组变成 [0, 3, 1, 2, 0] 。
     * - 选择 [0, 3, 1, 2, 0] 和 k = 0 。将 2 个数字都减去 20 ，子数组变成 [0, 2, 0, 2, 0] 。
     * - 选择 [0, 2, 0, 2, 0] 和 k = 1 。将 2 个数字都减去 21 ，子数组变成 [0, 0, 0, 0, 0] 。
     * \
     *
     * @param args args
     */
    public static void main(String[] args) {
        BeautifulSubarrays beautifulSubarrays = new BeautifulSubarrays();
        int[] arr = new int[]{4, 3, 1, 2, 4};
        System.out.println(beautifulSubarrays.beautifulSubarrays(arr));
    }

    /**
     * 美丽子阵列
     * \
     * 如果每一列都有偶数个 1，那么所有数的异或和必然等于 0。
     * 如果某一列有奇数个 1，那么所有数的异或和必然不等于 0。
     * 所以美丽子数组等价于：
     * <p>
     * 子数组的异或和等于 0。
     * \
     *
     * @param nums nums
     * @return long
     */
    public long beautifulSubarrays(int[] nums) {
        long ans = 0;
        int s = 0;
        //使用哈希表 cnt 记录每个异或累积值出现的次数，初始时将0放入哈希表
        Map<Integer, Integer> cnt = new HashMap<>();
        cnt.put(0, 1);
        for (int num : nums) {
            s ^= num;
            int count = cnt.getOrDefault(s, 0);
            ans += count;
            cnt.put(s, count + 1);
        }
        return ans;
    }

}
